\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\textbf{可持久化并查集 = 可持久化数组+并查集 = 主席树维护叶子结点 +
并查集}

且该并查集的合并必须是\textbf{按秩合并}

解释下不能使用路径压缩的原因：

\begin{itemize}
\item
  因为路径压缩时，再次调用 \(find\) 后，是要更新一部分值的
\item
  在数组上搞这些操作倒是挺快，然而在主席树里，每次找一个 \(farther\) 要
  \(log\) 次
\item
  把这个节点更新又要新建 \(log\) 个节点，一共要循环找不满
  \(log\)次，理论上时间复杂度是 \(O(Mlog^2N)\)的
\item
  但空间也是 \(O(Mlog^2N)\)，所以直接 \(GG\)
\end{itemize}

\end{document}
